package Crist;
import java.util.*;

import dominio.*;

/**
 * Clase que contiene todos los procedimientos necesarios para el algoritmo de Christofides.
 *
 * @author      Javier Gárate
 */

public class Christofides{

    private boolean ayudas;
    private Integer cost;

    /**
     * Constructor de la clase.
     *
     * @param ayudas   True or false, depende de si quieres que el programa escriba por terminal los pasos.
     */

    public Christofides(boolean ayud){
				this.ayudas=ayud;
				cost = 0;
    }

    /**
     * Procedimiento que a partir de un Graph g, devuelve una cadena de enteros, 
     * que representan los ids de los nodos a visitar
     *
     * @param g			Grafo con la lista de Nodes, y cada Nodes con sus costes asociados.
     * @return          El camino, nodo a nodo.
     */

    public Integer[] solve(Graph g){
    	System.out.println("CRISTOFIDES");
    	System.out.println("Matriz de Costes");
		// Matriz de pesos [i][j] = Peso de la arista que va del nodo i al j
		Integer[][] MatrizdePesos = ConstruirMatrizPesosdesdeGrafo(g);
		
		System.out.println("Arbol Recubridor Minimo");
		// mst => Arbol de Expansion Minima para g, calculado con el Algoritmo de Prim
		int mst[]=prim(MatrizdePesos,g.GetNumberNodes());
		
		System.out.println("Aparejando");
		// Match[][] => Apareamiento perfecto de minimo peso sobre los vertices 
		int match[][] = Aparejar(mst,MatrizdePesos,g.GetNumberNodes());
		
		System.out.println("MultiGrafo");
		// nodes [] => Multigrafo combinando las aristas generadas en mst y match
		GraphNode nodes[] = MultiGrafo(match, mst);
		
		System.out.println("Euleriano");
		// ruta[] => Circuito euleriano -> Circuito hamiltoniano (Eliminando nodos visitados)
		Integer ruta[] = getEulerCircuit(nodes);
		
		// Calculamos el coste total de recorrer la ruta
		cost = 0;
		for(int i=1;i<ruta.length;i++){
			cost+=MatrizdePesos[ruta[i-1]][ruta[i]];
		}
		cost+=MatrizdePesos[ruta[0]][ruta[ruta.length-1]];
		//System.out.println("Total: "+sum);
		
		return ruta;
	}
    
    
    
    public Integer getCost() {
		return cost;
	}
    
    

	/**
     * Procedimiento que a partir de un Graph g, genera la matriz de pesos, 
     * que representan los ids de los nodos a visitar
     *
     * @param g			Grafo con la lista de Nodes, y cada Nodes con sus costes asociados.
     * @return          Matrizdepesos [i][j] = Peso de la arista que va del nodo i al j
     */
	private Integer[][] ConstruirMatrizPesosdesdeGrafo(Graph g) {
		int dim = g.GetList().size();
		System.out.println("Taman: "+dim);
		Integer[][] wt = new Integer[dim][dim];
		for (Nodes n : g.GetList()) {
			for (Cost c : n.GetCosts()) {
				//System.out.println("Accedo a: "+n.id + " " +c.GetId());
				wt[n.id][c.GetId()] = c.GetCost();
			}
			wt[n.id][n.id] = 0;
		}
		return wt;
	}

		/**
     * Genera el Circuito Euleriano a partir del Multigrafo resultado de la union entre MST y MATCH
     *
     * @param nodes	    Multigrafo con el confunto de nodos de grado impar
     * @return          Circuito Euleriano descartando los nodos visitados (Hamiltoniano)
     */

		private Integer[] getEulerCircuit(GraphNode nodes[]) {
			LinkedList path=new LinkedList();
			Vector tmpPath = new Vector();
			int j=0;
			
			// Primer nodo
			nodes[0].getNextChild( nodes[0].getName(), tmpPath, true );
			path.addAll(0, tmpPath);
			
			// Recorre los nodos de nuestro camino
			while(j < path.size()) {
				if(nodes[((Integer)path.get(j)).intValue()].hasMoreChilds()) {
					nodes[((Integer)path.get(j)).intValue()].getNextChild( nodes[((Integer)path.get(j)).intValue()].getName(),tmpPath,true );
					if(tmpPath.size()>0) {
						for(int i = 0; i < path.size(); i++) {
							if( ((Integer)path.get(i)).intValue() == ((Integer)tmpPath.elementAt(0)).intValue() ) {
								path.addAll(i, tmpPath);
								break;
							}
						}
						tmpPath.clear();
					}
					j = 0;
				}
				else j++;
			}
			boolean inPath[]=new boolean[nodes.length];
			Integer[] route=new Integer[nodes.length];
			j=0;
			for(int i=0;i<path.size();i++){
				if(!inPath[((Integer)path.get(i)).intValue()]){
					route[j]=((Integer)path.get(i)).intValue();
					j++;
					inPath[((Integer)path.get(i)).intValue()]=true;
				}
			}

			return route;				
		}

		/**
		 * Genera el Multigrafo resultado de la union entre MST y MATCH
		 *
		 * @param match	    apareamiento perfecto M de mínimo peso en el grafo completo sobre el conjunto de vértices de grado impar en mts
		 * @param mst		Arbol recubridor minimo del grafo
		 * @return          Matriz unidimensional de nodos representando el multigrafo
		 */

		private GraphNode[] MultiGrafo(int[][] match, int[] mst) {
				GraphNode nodes[]=new GraphNode[mst.length];
				// Crear nodos vacios
				for(int i=0;i<mst.length;i++){
						nodes[i]=new GraphNode(i);
				}
				
				// Agregar nodos y aristas del mst
				for(int i=1;i<mst.length;i++){
						nodes[i].addChild(nodes[mst[i]]);
						nodes[mst[i]].addChild(nodes[i]);
				}
				
				// Agregar nodos y aristas del match
				for(int i=0;i<match.length;i++){
						nodes[match[i][0]].addChild(nodes[match[i][1]]);
						nodes[match[i][1]].addChild(nodes[match[i][0]]);
						if(ayudas) System.out.println(match[i][0]+"-"+match[i][1]);
				}
				
				return nodes;
		}

    /**
     * Calcular el Arbol Recubridor Minimo a traves del algoritmo de Prim.
     *
     * @param wt        Matriz de pesos.
     * @param dim       Numero de nodos.
     * @return          Vector de padres. p[i] es el identificador del nodo padre de i.
     */
    public int[] prim(Integer[][] wt,int dim){

				Vector queue=new Vector();
				for(int i=0;i<dim;i++)
						queue.add(new Integer(i));

				// Algoritmo de Prim
				boolean isInTree[] = new boolean[dim];
				Integer key[]=new Integer[dim];
				int p[]=new int[dim];

				for(int i=0;i<dim;i++){
					key[i]=Integer.MAX_VALUE;
				}

				key[0]=0; // raiz
				int u=0;

				Integer temp;
				Integer elem;
				do{
					isInTree[u] = true; // Añadir el nodo al arbol
					queue.removeElement(new Integer(u));
					for(int v=0;v<dim;v++){ 
							if( !isInTree[v] && wt[u][v]<key[v] ){
									p[v]=u;
									key[v]=wt[u][v];
							}
					}

					// Se queda con el cmaino mas corto
					Integer mint=Integer.MAX_VALUE;
					for(int i=0;i<queue.size();i++){
							elem=(Integer)queue.elementAt(i);
							temp=key[elem.intValue()];
							if(temp<mint){
									u=elem.intValue();
									mint=temp;
							}
					}
				} while(!queue.isEmpty());

				if(ayudas){
						System.out.print("Key-vektor: ");
						for(int i=0;i<dim;i++){
								System.out.print(key[i]+" ");
						}
						System.out.print("\n\n");
						System.out.print("Parent:     ");
						for(int i=0;i<dim;i++){
								System.out.print(p[i]+" ");
						}
						System.out.print("\n");
						Integer sum=0;
						for(int g=0;g<dim;g++){
								sum+=key[g];
						}

						System.out.println("\n\n"+sum);
				}
				
				return p;
    }

    /**
     * Encuentra una coincidencia entre los nodos que tienen un número impar de aristas
     *
     * @param p			p[i] es el identificador del nodo padre de i.
     * @param wt		Matriz de pesos del grafo.
     * @param dim		Numero de nodos.
     * @return 		   	Matriz bidimensional de pares. Dos columnas, cada fila representa un par
     */
    public int[][] Aparejar(int[] p,Integer[][] wt,int dim){

		Node nodes[] = new Node[p.length];

		// Creamos el bosque
		nodes[0] = new Node(0, true); // Raiz
		for(int i =1; i<p.length;i++) {
				nodes[i] = new Node(i,false);
		}

		// Contruimos los arboles
		for(int i = 0; i<p.length;i++) {
				if(p[i]!=i)
						nodes[p[i]].addChild(nodes[i]);
		}

		// Encontramos los nodos de grado impar
		ArrayList oddDegreeNodes = findOddDegreeNodes(nodes[0]);
		int nOdd = oddDegreeNodes.size();

		if(ayudas) {
				System.out.println("Nodos Impares:");
				for(int i = 0; i < nOdd; i++)
						System.out.print(oddDegreeNodes.get(i)+", ");
				System.out.println();
		}

		// Intentamos encontrar un matching minimo con un greedy para ordenar las aristas entre nodos de grado impar
		Arista Aristas[][] = new Arista[nOdd][nOdd];
		for(int i = 0; i < nOdd; i++) {
			for(int j = 0; j < nOdd; j++) {
				if( ( (Integer)oddDegreeNodes.get(i)).intValue()!= ((Integer)oddDegreeNodes.get(j)).intValue() )
						Aristas[i][j] = new Arista( ((Integer)oddDegreeNodes.get(i)).intValue(),
							((Integer)oddDegreeNodes.get(j)).intValue(),
								wt[((Integer)oddDegreeNodes.get(i)).intValue()][((Integer)oddDegreeNodes.get(j)).intValue()] );
				else
					Aristas[i][j] = new Arista( ((Integer)oddDegreeNodes.get(i)).intValue(),
							((Integer)oddDegreeNodes.get(j)).intValue(),Integer.MAX_VALUE );
			}
			Arrays.sort(Aristas[i]); // Ordenar todas las aristas del nodo i
		}
		/*Integer a,b,w;
		for(int i = 0; i < nOdd; i++) {
			a = ((Integer)oddDegreeNodes.get(i)).intValue();
			for(int j = 0; j < nOdd; j++) {
				b = ((Integer)oddDegreeNodes.get(j)).intValue();
				w = wt[i][j];
				if( a != b ) Aristas[i][j] = new Arista(a,b,w);
				else Aristas[i][j] = new Arista(a,b,Integer.MAX_VALUE );
			}
			Arrays.sort(Aristas[i]); //sortera alla kanter från nod i
		}*/

		boolean matched[] = new boolean[dim];
		int match[][] = new int[(nOdd/2)][2];

		// De cada nodo cogemos la arista mas corta
		int k = 0;
		for(int i = 0; i < nOdd; i++) {
			for(int j = 0; j < nOdd; j++) {
				if( matched[Aristas[i][j].getFrom()] || matched[Aristas[i][j].getTo()] )
					continue;
				else {
					//System.out.println("i = " + i +" j = " + j +" nodd = " + nOdd);
					matched[Aristas[i][j].getFrom()] = true;
					matched[Aristas[i][j].getTo()] = true;
					//System.out.println("k = " + k);
					match[k][0] = Aristas[i][j].getFrom();
					match[k][1] = Aristas[i][j].getTo();
					k++;
				}
			}
		}

		if(ayudas) {
			System.out.println("Matchning");
			for(int i = 0; i < nOdd/2; i++) {
				System.out.println(match[i][0] + "-" + match[i][1]);
			}
		}

		return match;
	}

    /**
     * Devuelve los nodos que tienen un numero impar de aristas
     *
     * @param _root     Nodo inicial.
     * @return          Lista de nodos con un numero impar de aristas.
     */

    private ArrayList findOddDegreeNodes(Node _root) {
		ArrayList oddNodes = new ArrayList();
		_root.visitFindOddDegreeNodes(oddNodes);
		return oddNodes;
    }
}